package main

import (
	"fmt"
	"math/rand"
	"time"
)

func sort(nums *[]int, start int, end int) {
	if start >= end {
		return
	}

	left := start
	right := end
	pivot := (*nums)[left]

	for left <= right {
		for (*nums)[left] < pivot {
			left++
		}

		for (*nums)[right] > pivot {
			right--
		}

		if left <= right {
			(*nums)[left], (*nums)[right] = (*nums)[right], (*nums)[left]
			left++
			right--
		}
	}

	sort(nums, start, right)
	sort(nums, left, end)
}

// [4, 9, 6, 2, 1, 3]
func quickSort(nums *[]int) {
	if nums == nil || len(*nums) == 0 {
		return
	}

	sort(nums, 0, len(*nums)-1)
}

func main() {
	nums := make([]int, 100)

	startTime := time.Now()

	for i := 0; i < 1; i++ {
		for i := 0; i < len(nums); i++ {
			nums[i] = rand.Intn(100)
		}

		quickSort(&nums)
	}

	endTime := time.Now()

	fmt.Println(nums)
	fmt.Println("time: ", endTime.Sub(startTime))
}
